package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-06
 * Time:20:07
 */

/**
 * 力扣面試经典150:198. 打家劫舍
 * 中等
 * 相关标签
 * 相关企业
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * 示例 1：
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *      偷窃到的最高金额 = 1 + 3 = 4 。
 */
public class rob {
    public static void main(String[] args) {
        System.out.println(rob(new int[]{2,1,1,2}));
    }
//    public static int rob(int[] nums) {
//        // 自顶向下递归改为自底向上递推，从初始位置直接开始正向推算，但空间复杂度还是O(n)。
//        int n = nums.length;
//        // 由于计算cache[0]cache[1]时会出现数组下标为负的情况，所以将cache数组直接设定为n+2长，从cache[2]作为计算起点，之前的0和1位默认为零凑位，防止下标越界。
//        int[] cache = new int[n + 2];
//        for(int i = 0; i < n; ++i){
//            cache[i + 2] = Math.max(cache[i + 1], cache[i] + nums[i]);
//        }
//        return cache[n + 1];
//    }
        public static int rob(int[] nums) {
            // 滚动数组：递推再次优化空间，使用O(1)级别额外空间解决（舍弃cache数组，用两个临时变量交替存储i位及i+1位）
            int n = nums.length;
            int pre1 = 0, pre2 = 0, res = 0;
            for(int i = 0; i < n; ++i){
                res = Math.max(pre2, pre1 + nums[i]);
                pre1 = pre2;
                pre2 = res;
            }
            return res;
        }
}
